//
// Created by Administrator on 2021/4/9.
//

/*
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。


示例：

输入：

1
\
     3
/
2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <iostream>
#include <climits>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
public:
    int ans = INT_MAX, former = -1, current = 0;

    // 暴力：全搜索，排序，找到最小差值
    // 注意二叉搜索树性质
    // 中序遍历就是一个有序数列
    // 在这个有序数列中找到最小差值就可以了
    int getMinimumDifference(TreeNode *root) {
        dfs(root);
        return ans;
    }

    void dfs(TreeNode *root) {
        if (!root) {
            return;
        }
        dfs(root->left);
        update(root->val);
        dfs(root->right);
    }

    void update(int x) {
        if (former >= 0) {
            former = current;
            current = x;
            ans = min(ans, current - former);
        } else {
            former = current;
            current = x;
        }
    }
    // AC
};
class Solution2 { // 题解 中序遍历
public:
    void dfs(TreeNode* root, int& pre, int& ans) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left, pre, ans);
        if (pre == -1) {
            pre = root->val;
        } else {
            ans = min(ans, root->val - pre);
            pre = root->val;
        }
        dfs(root->right, pre, ans);
    }
    int getMinimumDifference(TreeNode* root) {
        int ans = INT_MAX, pre = -1;
        dfs(root, pre, ans);
        return ans;
    }
};

int main() {
    auto t3 = TreeNode(7);
    auto t2 = TreeNode(4);
    auto t1 = TreeNode(5, &t2, &t3);
    Solution sol;
    cout << sol.getMinimumDifference(&t1);
    return 0;
}
